{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "关灯   \n",
    "小明正值班，突然发现他所在的屋子进水了，水面一直上涨，考虑到可能有电器暴露在水中，小明想通过尚未被水淹没的箱子达到电源处，关闭电源。假设电源和小明所处的位置都比较安全，不会被水淹没。已知屋子为矩形，可划分为大小相当的小方格，小明的位置，电源，箱子都正好在小方格的正中间，覆盖整个方格;小明每单位时间可以从一个小方格移动到相邻的处在同一行或者同一列的另一个小方格。为了安全小明只能移动到没有被上涨的水面淹没的小方格，箱子的高度不一，所在方格被水淹没的时间取决于方格内箱子的高度。水面每单位时间上涨1，如果此时箱子的高度小于或者等于水面的高度，则被淹没。请帮小明设计一条路线到达电源处，如果没有这样的路线，则小明应该待在原地。\n",
    "\n",
    "输入\n",
    "第一行:开始时水的深度\n",
    "第二行: 用空格隔开的两个数字，第一个为屋子的长，对应余下输入的行数，第二个为屋子的宽，对应余下输如中各行的的个数\n",
    "从第三行开始，描述屋子内小方格的布局。用非0数字代表箱子的高度，0代表没有箱子，s代表小明的位置，t代表电源位置\n",
    "输出\n",
    "输出一个字符串，起点为s，终点为t，中间为经过的箱子的高度，用空格分开"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "输入：\n",
    "0\n",
    "4 4\n",
    "s 1 3 5\n",
    "2 3 2 4\n",
    "2 4 4 5\n",
    "3 5 7 t\n",
    "输出：\n",
    "s 2 3 4 5 7 t "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Read input\n",
    "initial_water_depth = int(input())\n",
    "n, m = map(int, input().split())\n",
    "grid = []\n",
    "s_pos = None\n",
    "t_pos = None\n",
    "box_heights = {}\n",
    "for i in range(n):\n",
    "    row = input().split()\n",
    "    for j, val in enumerate(row):\n",
    "        if val == 's':\n",
    "            s_pos = (i, j)\n",
    "            box_heights[(i, j)] = float('inf')  # s is always safe\n",
    "        elif val == 't':\n",
    "            t_pos = (i, j)\n",
    "            box_heights[(i, j)] = float('inf')  # t is always safe\n",
    "        else:\n",
    "            box_heights[(i, j)] = int(val)\n",
    "    grid.append(row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "initial_water_depth=0\n",
    "n,m=4,4\n",
    "\n",
    "# grid = [\n",
    "#     ['s', 1, 3, 5],\n",
    "#     [2, 3, 2, 4],\n",
    "#     [2, 4, 4, 5],\n",
    "#     [3, 5, 7, 't']\n",
    "# ]\n",
    "\n",
    "grid = [\n",
    "    ['s', 1, 3, 5],\n",
    "    [2, 3, 2, 4],\n",
    "    [2, 4, 4, 5],\n",
    "    [3, 5, 5, 't']\n",
    "]\n",
    "\n",
    "\n",
    "box_heights = {}\n",
    "for i in range(n):\n",
    "    for j in range(m):\n",
    "        val = grid[i][j]\n",
    "        if val == 's':\n",
    "            s_pos = (i, j)\n",
    "            box_heights[(i, j)] = float('inf')  # s is always safe\n",
    "        elif val == 't':\n",
    "            t_pos = (i, j)\n",
    "            box_heights[(i, j)] = float('inf')  # t is always safe\n",
    "        else:\n",
    "            box_heights[(i, j)] = int(val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "s\n"
     ]
    }
   ],
   "source": [
    "# Precompute submerged times\n",
    "# 初始化，剩余时间\n",
    "submerged_time = {}\n",
    "for pos, height in box_heights.items():\n",
    "    if height == float('inf'):\n",
    "        submerged_time[pos] = float('inf')\n",
    "    else:\n",
    "        submerged_time[pos] = height - initial_water_depth\n",
    "        if submerged_time[pos] <= 0:\n",
    "            submerged_time[pos] = -1  # Already submerged\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "queue = deque()\n",
    "queue.append((s_pos[0], s_pos[1], 0)) # 初始化队列\n",
    "visited = {}\n",
    "visited[(s_pos[0], s_pos[1])] = 0\n",
    "parent = {}\n",
    "found = False\n",
    "\n",
    "while queue:\n",
    "    x, y, time = queue.popleft()\n",
    "    if (x, y) == t_pos: # \n",
    "        found = True\n",
    "        final_time = time\n",
    "        break\n",
    "    for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:\n",
    "        nx, ny = x+dx, y+dy\n",
    "        if 0 <= nx < n and 0 <= ny < m and (nx, ny) in box_heights:\n",
    "            next_time = time + 1\n",
    "            cell_submerged_time = submerged_time.get((nx, ny), -1)\n",
    "            if cell_submerged_time == -1 or next_time >= cell_submerged_time:\n",
    "                continue  # Cannot move to submerged cell\n",
    "            if (nx, ny) not in visited or next_time < visited[(nx, ny)]:\n",
    "                visited[(nx, ny)] = next_time\n",
    "                parent[(nx, ny)] = (x, y)\n",
    "                queue.append((nx, ny, next_time))\n",
    "\n",
    "if found:\n",
    "    path = []\n",
    "    pos = t_pos\n",
    "    while pos != s_pos:\n",
    "        path.append(pos)\n",
    "        pos = parent[pos]\n",
    "    path.append(s_pos)\n",
    "    path.reverse()\n",
    "    output = []\n",
    "    for pos in path:\n",
    "        val = grid[pos[0]][pos[1]]\n",
    "        if val == 's' or val == 't':\n",
    "            output.append(val)\n",
    "        else:\n",
    "            output.append(str(box_heights[pos]))\n",
    "    print(' '.join(output))\n",
    "else:\n",
    "    # Xiao Ming should stay in place\n",
    "    print('s')\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "base",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
